W4. Regular Language Closure

1. Theory

1.1 Representations of Finite State Automata

In previous lectures, we learned the formal definition of a Finite State Automaton (FSA). Now we explore two important variations in how the transition function can be defined: complete and incomplete FSAs.

1.1.1 Complete FSAs

A complete FSA is one where the transition function is total, meaning it is defined for every possible combination of state and input symbol. Formally, for a complete FSA , the transition function must satisfy:

This means that no matter what state the automaton is in and what symbol it reads, there is always a defined transition to some state (which could be the same state via a self-loop).

Why is completeness important? A complete FSA guarantees that every string over the alphabet can be processed without getting “stuck.” The automaton will always have a well-defined final state, which is either accepting or rejecting.

Example: Consider an FSA over alphabet with two states (accepting) and (non-accepting):

• From : on input 0 → stay in , on input 1 → go to
• From : on input 0 → go to , on input 1 → stay in

This is complete because every combination has a defined transition.

1.1.2 Incomplete FSAs

An incomplete FSA (also called a partial FSA) is one where the transition function is partial, meaning some combinations of state and input symbol have no defined transition. Formally:

What happens when we reach an undefined transition? When processing a string, if the FSA encounters a situation where is undefined, the string is automatically rejected—the automaton cannot continue processing and therefore cannot reach an accepting state.

Example: Consider an FSA over alphabet :

• (start) → on ‘a’ go to ; on ‘b’ undefined
• (accept) → on ‘b’ stay in ; on ‘a’ undefined

This FSA accepts strings matching the pattern “a” followed by zero or more ‘b’s (). Any string starting with ’b’ or containing ‘a’ after the first position will hit an undefined transition and be rejected.

Graphical Representation: In state diagrams, incomplete FSAs simply omit arrows for undefined transitions. Complete FSAs show all possible transitions.

1.1.3 Converting Incomplete FSAs to Complete FSAs

Any incomplete FSA can be converted to an equivalent complete FSA by adding a trap state (also called an error state or sink state). The process is:

1. Add a new non-accepting state (or for “error”)
2. For every undefined transition , define it to go to the trap state:
3. Add self-loops on the trap state for all symbols: for all

The trap state has a special property: once entered, the automaton can never leave. Since it’s non-accepting, any string that leads to it will be rejected.

Example: Converting the incomplete FSA from above:

• Add (non-accepting)
• on ‘b’ →
• on ‘a’ →
• on ‘a’ →
• on ‘b’ →

Now every state-symbol combination has a defined transition, making the FSA complete while preserving the language it recognizes.

1.2 Regular Languages

A regular language is any language that can be recognized (accepted) by a finite state automaton. This is a fundamental concept in theoretical computer science.

Formal Definition: A language is called regular if and only if there exists a finite state automaton such that , where:

Here, consists of exactly those strings that, when processed by , lead to an accepting state.

Important Properties of Regular Languages:

1. Decidability: For any regular language and any string , we can algorithmically determine whether by simulating the FSA
2. Finiteness of description: Regular languages can be described by FSAs with finitely many states
3. Closure properties: Regular languages are closed under many operations (union, intersection, complement, concatenation, Kleene star)

Examples of Regular Languages:

• (regular)
• (regular)
• (NOT regular—requires counting, which FSAs cannot do)

1.3 Operations on Finite State Automata

One of the most powerful properties of regular languages is that they are closed under various operations. This means that if we apply these operations to regular languages, the result is still a regular language. We can construct FSAs for the resulting languages using systematic methods.

1.3.1 Complement

Problem: Given an FSA that accepts language , construct an FSA that accepts the complement (all strings NOT in ).

Key Idea: To accept the opposite language, we “flip” the accepting and non-accepting states. A string previously accepted should now be rejected, and vice versa.

Construction for Complete FSAs:

Given a complete FSA , the complement automaton is:

where (the set of states that were NOT accepting in ).

Everything stays the same except the accepting states are flipped.

Example: Consider an FSA over with states :

• : , with (accepts strings with odd length)
• : Same transitions, but (accepts strings with even length, including )

Why Does This Work? In a complete FSA, every string leads to some final state. If that state was accepting in , we want to reject it in , so we make it non-accepting. If it was non-accepting in , we want to accept it in , so we make it accepting.

Critical Requirement: Completeness

The simple “flip accepting states” approach only works for complete FSAs. Why?

In an incomplete FSA, some strings cause undefined transitions and are implicitly rejected (they don’t reach any state). When we flip accepting states, we’re only changing what happens to strings that DO complete processing. We’re not addressing strings that were rejected due to undefined transitions.

Construction for Incomplete FSAs:

To construct the complement of an incomplete FSA:

1. First, make the FSA complete by adding a trap state for all undefined transitions
2. Then, flip the accepting states:

Example: Incomplete FSA: (accepting), with over alphabet .

Step 1: Add trap state . Define:

• on ‘b’ →
• on ‘a’ →
• on ‘a’, ‘b’ →

Step 2: Flip accepting states. Original , so .

The complement FSA accepts all strings except those starting with ‘a’ and continuing with only ’b’s.

1.3.2 Intersection

Problem: Given two FSAs and accepting languages and respectively, construct an FSA accepting (strings in BOTH languages).

Key Idea: We run both FSAs in parallel on the same input. We accept a string only if it would be accepted by BOTH individual FSAs.

Construction (Product Construction):

Given:

The intersection automaton is:

where:

• (Cartesian product: pairs of states)
• (pair of initial states)
• (transition in both simultaneously)
• (BOTH must be accepting)

Intuition: Each state represents “ is in state AND is in state .” When we read a symbol, we update both components. We accept only when both components are in their respective accepting states.

Example:

accepts strings with odd number of symbols (over ):

• States:
• Transitions: ,
• Accepting:

accepts all strings (over ):

• States:
• Transitions:
• Accepting:

Product automaton :

• States:
• Transitions: ,
• Accepting: (where and )

This accepts strings with odd number of symbols (same as , since accepts everything).

Size: If and , the product automaton has states. Not all may be reachable from the initial state, so we can often simplify by removing unreachable states.

1.3.3 Union

Problem: Given two FSAs and accepting languages and , construct an FSA accepting (strings in EITHER language).

Construction:

The construction is almost identical to intersection, except for the accepting states:

where:

• (EITHER can be accepting)

The only difference from intersection is the accepting condition: We use logical OR () instead of AND ().

Example: Using the same and from the intersection example:

• Accepting states: (since , both states qualify)
• The initial state is accepting, so even is accepted
• This accepts all strings (same as )

Alternative Construction Using De Morgan’s Laws:

We can also construct union using complement and intersection:

This means: “NOT (NOT AND NOT )” = “anything not excluded by both” = “accepted by at least one.”

1.3.4 Difference

Problem: Given two FSAs and accepting languages and , construct an FSA accepting (strings in but NOT in ).

Construction:

Again using the product construction:

where:

• (in AND not in )

Intuition: We accept only when “ accepts” AND “ rejects.”

Example:

accepts odd-length strings, accepts all strings (from before).

• (nothing is in but not in , since is everything)
• Accepting: (no state satisfies , since and all reachable states have )

Reversed Example: (all strings except odd-length):

• Accepting: (where and )
• This accepts even-length strings (including )

1.4 Finite State Transducers

A Finite State Transducer (FST) extends the concept of a finite state automaton by adding an output capability. While an FSA only accepts or rejects strings, an FST transforms input strings into output strings.

1.4.1 Formal Definition

A Finite State Transducer is a tuple:

where:

• is a standard FSA (the “acceptance” component)
• is the output alphabet (a finite set of symbols for output)
• is the output function that maps each transition to a string of output symbols (possibly empty)

Key Points:

1. Translation is performed only on accepted strings: If the input string is not accepted by the underlying FSA, no output is produced (or the transducer fails)
2. Each transition can produce output: When transitioning from state on input , the transducer outputs
3. Output can be empty (): Some transitions produce no output

Graphical Representation: In diagrams, transitions are labeled as where is the input symbol and is the output string.

1.4.2 Example: Removing Odd Occurrences of 0 and Doubling 1s

Problem: Build an FST over alphabet that:

• Accepts strings with an even number of 0’s
• Outputs a transformed string where:
  • Every odd occurrence of 0 is removed (outputs )
  • Every even occurrence of 0 is kept (outputs 0)
  • Every 1 is doubled (outputs 11)

Examples:

• Input: “010010” → Output: “110110”
  • 0 (1st, odd) →
  • 1 → 11
  • 0 (2nd, even) → 0
  • 0 (3rd, odd) →
  • 1 → 11
  • 0 (4th, even) → 0
• Input: “00” → Output: “0”
  • 0 (1st, odd) →
  • 0 (2nd, even) → 0
• Input: “000100011” → Output: “011001111”
  • 0 (odd) → , 0 (even) → 0, 0 (odd) → , 1 → 11, 0 (even) → 0, 0 (odd) → , 0 (even) → 0, 1 → 11, 1 → 11

FST Construction:

• States:
  • (accepting): “Seen an even number of 0’s”
  • : “Seen an odd number of 0’s”
• Transitions and Outputs:
  • (loop: reading 1, output 11, stay in even state)
  • (reading 1st/3rd/… 0, output nothing, go to odd state)
  • (loop: reading 1, output 11, stay in odd state)
  • (reading 2nd/4th/… 0, output 0, return to even state)
• Accepting states: (even number of 0’s)

How it works: The transducer tracks parity (even/odd count) of 0’s using states. Each transition specifies what to output. For 1’s, output is always “11”. For 0’s, output depends on whether it’s an odd occurrence () or even occurrence (0).

1.4.3 Applications of FSTs

FSTs are used in many practical applications:

• Text processing: Find-and-replace operations, spell correction
• Natural language processing: Morphological analysis (e.g., converting “walked” to “walk”)
• Compilers: Translating source code patterns to target code
• Data compression: Encoding/decoding schemes
• Regular expression replacement: Implementing operations like s/pattern/replacement/g

1.5 Closure Properties of Regular Languages

A family of languages is closed under an operation OP if: whenever languages , the result is also in .

What does closure mean intuitively? Think of a set being “closed” like a closed system in physics—no matter what operations you perform inside the system, you never leave it. For languages, if you start with regular languages and apply certain operations, you get back regular languages.

Regular languages are closed under:

1. Union: is regular (proven by product construction)
2. Intersection: is regular (proven by product construction)
3. Complement: is regular (proven by flipping accepting states in complete FSA)
4. Difference: is regular (proven by product construction)
5. Concatenation: is regular
6. Kleene star: is regular

Why is closure important?

1. Compositional reasoning: We can build complex regular languages from simpler ones
2. Proving regularity: If we know and are regular, we immediately know is regular without constructing an FSA
3. Compiler design: Combining patterns to recognize complex tokens

Example: The language is regular because:

• is regular
• is regular
• is regular (by closure under union)

1.6 Practical Considerations: Simplifying FSAs

When constructing FSAs using operations like intersection or union, the resulting automaton may have unreachable states—states that cannot be reached from the initial state. These can be removed without changing the language.

Example: In the product construction, if and , the product has states. But not all combinations may be reachable from the initial state .

Simplification algorithm:

1. Mark the initial state as reachable
2. Iteratively mark states reachable from already-marked states via any transition
3. Remove all unmarked states and their transitions

This process is important for practical implementation, as it reduces the size and complexity of the automaton.

---

2. Definitions

• Complete FSA: A finite state automaton where the transition function is total, meaning is defined for every state and every symbol .
• Incomplete FSA (Partial FSA): A finite state automaton where the transition function is partial, meaning some combinations of state and input symbol have no defined transition. Strings reaching undefined transitions are automatically rejected.
• Trap State (Error State, Sink State): A non-accepting state added to an incomplete FSA to make it complete. All undefined transitions lead to the trap state, which has self-loops for all input symbols, ensuring that once entered, the automaton remains there and rejects the string.
• Regular Language: A language that can be recognized (accepted) by some finite state automaton. Equivalently, is regular if there exists an FSA such that .
• Complement of a Language: For a language over alphabet , the complement (or ) is the set of all strings over that are not in : .
• Intersection of Languages: For languages and over the same alphabet, the intersection is the set of strings that belong to both languages: .
• Union of Languages: For languages and , the union is the set of strings that belong to at least one of the languages: .
• Difference of Languages: For languages and , the difference is the set of strings in but not in : .
• Product Construction: A method for combining two FSAs and into a single FSA whose states are pairs where and . The construction simulates running both automata in parallel on the same input.
• Cartesian Product of Sets: For sets and , the Cartesian product is the set of all ordered pairs.
• Finite State Transducer (FST): An extension of a finite state automaton that produces output strings in addition to accepting or rejecting input. Formally defined as where is the output alphabet and is the output function.
• Output Function (): In an FST, the function that specifies what output string (possibly empty) is produced when transitioning from a state on a given input symbol.
• Closure Property: A family of languages is closed under an operation if applying that operation to languages in produces another language in . Regular languages are closed under union, intersection, complement, difference, concatenation, and Kleene star.
• Unreachable State: A state in an FSA that cannot be reached from the initial state by any sequence of transitions. Unreachable states can be removed without changing the language accepted by the FSA.

---

3. Formulas

• Complement FSA (Complete): For a complete FSA , the complement is where
• Intersection FSA (Product Construction): For and , the intersection is where:
• Union FSA (Product Construction): Same as intersection except
• Difference FSA (Product Construction): Same as intersection except
• De Morgan’s Laws for Languages: and

---

4. Practice

4.1. Constructing an FST: Past Tense to Present Tense (Lab 4, Task 1)

Build a complete FST over alphabet that:

• Accepts only the verbs “walked” or “talked”
• Translates the input verb to present tense (removes the “ed”)

Click to see the solution

Key Concept: The FST reads the input character by character, outputting the appropriate transformation. For “walked” → “walk”, we output each letter except the final “ed”.

FST mapping walked/talked to walk/talk

1. Design the states:
   • (start): Haven’t seen anything yet
   • : Seen “w” or “t”
   • : Seen “wa” or “ta”
   • : Seen “wal” or “tal”
   • : Seen “walk” or “talk”
   • : Seen “walke” or “talke”
   • (accepting): Seen complete “walked” or “talked”
   • : Error state for invalid inputs
2. Define transitions and outputs:
   • From : on ‘w’ output ‘w’, go to ; on ‘t’ output ‘t’, go to ; else go to trap
   • From : on ‘a’ output ‘a’, go to ; else go to trap
   • From : on ‘l’ output ‘l’, go to ; else go to trap
   • From : on ‘k’ output ‘k’, go to ; else go to trap
   • From : on ‘e’ output , go to (don’t output ‘e’)
   • From : on ‘d’ output , go to (don’t output ‘d’)
   • is accepting
   • Trap state loops with no output

Verification:

• Input: “walked” → Output: “w” + “a” + “l” + “k” + + = “walk” ✓
• Input: “talked” → Output: “t” + “a” + “l” + “k” + + = “talk” ✓

Answer: The FST has states through with transitions as described, outputting each character except ‘e’ and ‘d’ at the end.

4.2. Constructing an FST: Erasing Every Second ‘a’ (Lab 4, Task 2)

Build a complete FST over alphabet that:

• Accepts only strings ending with the letter ‘b’
• Translates the input by erasing every second occurrence of ‘a’

Click to see the solution

Key Concept: Track the parity of ‘a’s seen so far. Output ’a’ on odd occurrences, erase (output ) on even occurrences. Always output ‘b’.

FST erasing every second a while requiring the string to end in b

1. Design states:
   • (start): Seen even number of ‘a’s, not ended with ’b’
   • : Seen odd number of ‘a’s, not ended with ’b’
   • (accepting): Seen even number of ‘a’s, ended with ’b’
   • (accepting): Seen odd number of ‘a’s, ended with ’b’
2. Transitions and outputs:
   • From : on ‘a’ output ‘a’, go to (first ‘a’, odd count); on ‘b’ output ‘b’, go to
   • From : on ‘a’ output , go to (second ‘a’, even count, erase); on ‘b’ output ‘b’, go to
   • From : on ‘a’ output ‘a’, go to ; on ‘b’ output ‘b’, stay in
   • From : on ‘a’ output , go to ; on ‘b’ output ‘b’, stay in
3. Accepting states: (ended with ‘b’)

Verification:

• Input: “aaab” → Outputs: ‘a’ (1st ‘a’), (2nd ‘a’), ‘a’ (3rd ‘a’), ‘b’ → “aab” ✓
• Input: “aabb” → Outputs: ‘a’, , ‘b’, ‘b’ → “abb” ✓

Answer: The FST has four states tracking parity of ‘a’s and whether the string ends with ’b’, with outputs as described.

4.3. Building FSAs for Even 1’s and Odd 0’s (Lab 4, Task 3)

Let be the alphabet.

Problem 1: Build a complete FSA that recognizes:

Problem 2: Build a complete FSA that recognizes:

Click to see the solution

Key Concept: Track parity (even/odd count) using two states. Reading the tracked symbol toggles the state.

Two parity FSAs: even number of 1s and odd number of 0s

(a) FSA for Even Number of 1’s ():

1. States:
   • (start, accepting): Even number of 1’s seen
   • : Odd number of 1’s seen
2. Transitions:
   • From : on ‘0’ stay in (0’s don’t affect count); on ‘1’ go to (even → odd)
   • From : on ‘0’ stay in ; on ‘1’ go to (odd → even)
3. Accepting:

Verification:

• ““: in → ACCEPT (zero 1’s is even) ✓
• “11”: → ACCEPT ✓
• “101”: → ACCEPT ✓
• “1”: → REJECT ✓

(b) FSA for Odd Number of 0’s ():

1. States:
   • (start): Even number of 0’s seen
   • (accepting): Odd number of 0’s seen
2. Transitions:
   • From : on ‘1’ stay in ; on ‘0’ go to (even → odd)
   • From : on ‘1’ stay in ; on ‘0’ go to (odd → even)
3. Accepting:

Answer:

• has states with accepting
• has states with accepting

4.4. Combining FSAs: Union, Intersection, Difference (Lab 4, Task 4)

Using the FSAs and from Example 4.11:

Problem 3: Build a complete FSA that accepts when EITHER OR accepts (union).

Problem 4: Build a complete FSA that accepts when BOTH AND accept (intersection).

Problem 5: Build a complete FSA that accepts when accepts AND rejects (difference).

Problem 6: Build a complement for .

Click to see the solution

Key Concept: Use product construction for all except complement. Accepting states differ based on the operation.

Product construction viewpoint for union, intersection, and difference

(Problem 3) Union:

1. Product construction:
   • Initial:
   • Transitions:
2. Accepting states (at least one component accepting):

Answer: The union FSA has 4 states with 3 accepting states: .

(Problem 4) Intersection:

1. Same product construction
2. Accepting states (both components accepting):

Answer: The intersection FSA has 4 states with 1 accepting state: .

(Problem 5) Difference:

1. Same product construction
2. Accepting states ( accepts, rejects):

Answer: The difference FSA has 4 states with 1 accepting state: .

(Problem 6) Complement:

1. is already complete (has transitions for all inputs)
2. Flip accepting states: Original Complement

Answer: has the same states and transitions as , but with (accepts odd number of 1’s).

4.5. Complement of Incomplete FSA (Lab 4, Task 5)

Construct a complement for the following incomplete FSA over alphabet :

• (start, accepting): loops on ‘1’; goes to on ‘0’
• : goes to on ‘0’; transition on ‘1’ is undefined

Click to see the solution

Key Concept: First complete the FSA, then flip accepting states.

Completing an incomplete FSA with a trap state before taking the complement

1. Add trap state for undefined transitions:
   • on ‘1’ →
   • on ‘0’ →
   • on ‘1’ → (self-loops)
2. Complete FSA:
   • States: (accepting),
   • All transitions defined
3. Flip accepting states: Original Complement

Answer: The complement FSA has states with accepting states .

4.6. FSAs for Divisibility by 2 and 3 (Lab 4, Task 6)

Let be the alphabet. Assume is part of both languages.

Problem 1: Build a complete FSA that recognizes:

Problem 2: Build a complete FSA that recognizes:

Click to see the solution

Key Concept: Divisibility can be determined by examining specific patterns in binary representation.

FSAs for divisibility by 2 and divisibility by 3 in binary

(a) Divisibility by 2:

A binary number is divisible by 2 if and only if its last digit is 0 (or it’s the empty string, representing 0).

1. States:
   • (start, accepting): Last digit seen is 0, or no digits yet ()
   • : Last digit seen is 1
2. Transitions:
   • From : on ‘0’ stay in (last digit is 0); on ‘1’ go to (last digit is 1)
   • From : on ‘0’ go to (last digit is 0); on ‘1’ stay in (last digit is 1)
3. Accepting:

Verification:

• → in → ACCEPT (represents 0, divisible by 2) ✓
• “10” (= 2) → → ACCEPT ✓
• “11” (= 3) → → REJECT ✓

(b) Divisibility by 3:

We track the remainder when the number is divided by 3. Reading binary digits left-to-right, we update the remainder using: .

1. States (represent remainder mod 3):

   • (start, accepting): Remainder is 0 (divisible by 3)
   • : Remainder is 1
   • : Remainder is 2

2. Transitions: From state , reading digit :

   • New state:

   Explicitly:

   • From : on ‘0’ → (); on ‘1’ → ()
   • From : on ‘0’ → (); on ‘1’ → ()
   • From : on ‘0’ → (); on ‘1’ → ()

3. Accepting:

Verification:

• → in → ACCEPT (0 divisible by 3) ✓
• “11” (= 3) → → ACCEPT ✓
• “110” (= 6) → → ACCEPT ✓
• “10” (= 2) → → REJECT ✓

Answer:

• has 2 states, accepting when last digit is 0
• has 3 states, accepting when remainder mod 3 is 0

4.7. Combining Divisibility FSAs (Lab 4, Task 7)

Using and from Example 4.14:

Problem 3: Build a complete FSA that accepts when BOTH and accept (divisible by both 2 and 3, i.e., divisible by 6).

Problem 4: Build a complete FSA that accepts when EITHER or accepts (divisible by 2 or 3).

Problem 5: Build a complete FSA that accepts when accepts and rejects (divisible by 2 but not 3).

Click to see the solution

Key Concept: Use product construction with appropriate accepting conditions.

Product automaton for combining divisibility by 2 and divisibility by 3

(Problem 3) Divisible by 6:

1. Product states: states Initial:
2. Accepting (divisible by both 2 and 3):

Answer: The FSA for divisibility by 6 has 6 states with 1 accepting state: .

(Problem 4) Divisible by 2 or 3:

1. Same product states
2. Accepting (divisible by 2 OR 3):

Answer: The FSA has 6 states with 4 accepting states.

(Problem 5) Divisible by 2 but not 3:

1. Same product states
2. Accepting (divisible by 2 AND NOT by 3):

Answer: The FSA has 6 states with 2 accepting states: and .

4.8. Complex Product Construction (Lab 4, Task 8)

Let and be the complete FSAs depicted over alphabet :

:

• States: (start), , (accepting)
• Transitions: loops on ‘b’, goes to on ‘a’; loops on ‘a’, goes to on ‘b’; goes to on ‘b’

:

• States: (start), , (accepting)
• Transitions: loops on ‘a’, goes to on ‘b’; goes to on ‘a’, goes to on ‘b’; loops on ‘a’ and ‘b’

Draw complete FSAs accepting:

(i) (ii) (iii)

Click to see the solution

Key Concept: Use product construction, then identify accepting states based on the operation.

(i) Union:

1. Product states: states Initial:

2. Accepting states (at least one component accepting):

   Explicitly:

3. Transitions: Apply for all states and symbols

Answer: 9-state FSA with 5 accepting states (all pairs where or ).

(ii) Intersection:

1. Same product construction
2. Accepting states (both components accepting):

Answer: 9-state FSA with 1 accepting state: .

(iii) Difference:

1. Same product construction
2. Accepting states ( accepts, rejects):

Answer: 9-state FSA with 2 accepting states: and .

4.9. Converting State Diagram to State Table (Tutorial 4, Example 1)

Given an FSA as a State Transition Diagram, build a State Transition Table.

The FSA has three states: (start), , and (accepting), over alphabet . Transitions:

• ,
• ,
• ,

Click to see the solution

Key Concept: A state transition table is an alternative representation of an FSA, showing transitions in tabular form. Rows represent states, columns represent input symbols, and entries show the destination state.

1. Create the table structure:
   • Rows: One for each state ()
   • Columns: One for each symbol in the alphabet ()
   • Mark the initial state with and accepting states with
2. Fill in transitions from the diagram:
   • From : on ‘a’ go to , on ‘b’ go to
   • From : on ‘a’ go to , on ‘b’ go to
   • From : on ‘a’ go to , on ‘b’ go to

State Transition Table:

	a	b

Answer: The completed state transition table is shown above.

4.10. Completing an Incomplete FSA (Tutorial 4, Example 2)

Given an incomplete FSA over alphabet :

• (start) (accepting)
• (accepting) (self-loop)

Transitions on ‘b’ from and ‘a’ from are undefined. Make this FSA complete.

Click to see the solution

Key Concept: To complete an FSA, add a trap state and define all missing transitions to lead to it.

1. Identify undefined transitions:
   • is undefined
   • is undefined
2. Add a trap state (non-accepting)
3. Define the missing transitions to go to the trap:
4. Add self-loops on the trap state for all symbols:

Complete FSA:

• States: (start), (accepting), (trap, non-accepting)
• Transitions:
  • ,
  • ,
  • ,

Answer: The completed FSA includes a trap state with all previously undefined transitions leading to it.

4.11. Complement of a Complete FSA (Tutorial 4, Example 3)

Given a complete FSA over alphabet :

This FSA accepts strings with an odd number of ’a’s. Construct , the complement.

Click to see the solution

Key Concept: For a complete FSA, the complement is obtained by flipping accepting and non-accepting states.

1. Identify the original accepting states:
2. Compute the complement set:
3. Construct the complement FSA:

Everything is the same except is replaced by .

Verification:

• Original accepts: “a”, “aaa”, “aaaaa”, … (odd lengths)
• Complement accepts: , “aa”, “aaaa”, … (even lengths, including zero)

Answer: which accepts strings with an even number of ’a’s.

4.12. Complement of an Incomplete FSA (Tutorial 4, Example 4)

Given an incomplete FSA over alphabet :

• (start) (accepting)
• (self-loop)

Construct the complement FSA.

Click to see the solution

Key Concept: For incomplete FSAs, we must first make them complete before computing the complement.

1. Make the FSA complete by adding a trap state:
   • Add state (trap)
   • (was undefined)
   • (was undefined)
   • , (self-loops)
2. The complete FSA has:
   • States:
   • Accepting states:
3. Compute the complement:

Complement FSA:

• States: (start, accepting), (non-accepting), (accepting)
• Same transitions as the completed version
• Accepting states:

Answer: The complement FSA accepts all strings except those of the form for .

4.13. Intersection of Two FSAs (Tutorial 4, Example 5)

Given:

• where , (accepts odd-length strings)
• where (accepts all strings)

Construct .

Click to see the solution

Key Concept: Use the product construction with accepting states being pairs where both components are accepting.

1. Determine the product states:
2. Determine the initial state:
3. Define transitions using :
4. Determine accepting states (both components must be accepting):

Product FSA:

where:

Answer: The intersection FSA accepts strings with odd length (same as , since accepts everything).

4.14. Intersection of Complex FSAs (Tutorial 4, Example 6)

Given two FSAs over alphabet :

:

• States: (start), , (accepting),
• Transitions: , ; , ; loops on ; loops on

:

• States: (start), , (accepting)
• Transitions: , ; , ; loops on

Construct and simplify by removing unreachable states.

Click to see the solution

Key Concept: Use product construction, then identify and remove unreachable states.

1. Build the full product automaton:

   • States: states total
   • Initial state:
   • Accepting states:

2. Determine transitions for all pairs: For example:

   • From on ‘a’:
   • From on ‘b’:
   • From on ‘a’: — this leads to the accepting state!

3. Identify reachable states from :

   To reach in : must go To reach in : must go (and loops on all symbols)

   Path for “aaba”: ✓

4. Simplified automaton (after removing unreachable states):

Answer: The simplified intersection FSA accepts strings that reach both in and in . A minimal accepting string is “aaba”.

4.15. Union of Two FSAs (Tutorial 4, Example 7)

Using the same and from Example 5 (odd-length strings and all strings), construct .

Click to see the solution

Key Concept: Use product construction with accepting states being pairs where at least one component is accepting.

1. Product states and transitions are the same as for intersection:

   • Initial:
   • Transitions:

2. Determine accepting states (at least one component accepting):

   Since and all reachable states have , we have for all states.

   Therefore: (both states are accepting)

3. Result: Since the initial state is accepting, even the empty string is accepted. In fact, every string is accepted.

Answer: accepts all strings over (same as , since and ).

4.16. Difference of Two FSAs (Tutorial 4, Example 8)

Compute where accepts odd-length strings and accepts all strings (from previous examples).

Click to see the solution

Key Concept: Accepting states are pairs where the first component is accepting and the second is NOT accepting.

1. Product construction (same states and transitions as before):
   • Initial:
2. Determine accepting states:
   • For : ✓ but ✗ (we need )
   • For : ✗
   • Result: (no accepting states)

Answer: because every string in is also in (since accepts everything).

4.17. Difference of Two FSAs (Tutorial 4, Example 9)

Compute (all strings minus odd-length strings).

Click to see the solution

1. Accepting states:
   • We need: AND
   • For : ✓ and ✓ → accepting
   • For : ✓ but ✗ → not accepting
   • Result:

Answer: accepts even-length strings (including ).